#include "DoubleLinkList.h"
#include <iostream>

// 无参构造
DoubleLinkList::DoubleLinkList():size(0)
{
    head = tail = new Node(0);
}

// 尾插
void DoubleLinkList::InsertTail(const ElementType &element)
{
    Node *newNode = new Node(element);
    tail->next = newNode;
    newNode->prev = tail;
    tail = newNode;
    size++;
}

// 头插
void DoubleLinkList::InsertHead(const ElementType &element)
{
    Node *newNode = new Node(element);
    newNode->next = head->next;
    newNode->prev = head;
    head->next = newNode;
    if(size != 0)
        newNode->next->prev = newNode;
    else
        tail = newNode;
    size++;
}

// 中间插
void DoubleLinkList::InsertByIndex(int index, const ElementType &element)
{
    if(index < 0 || index > size)
        return;
    Node *travelPoint = head;
    // index - 1的位置
    for(int i = 0; i < index; i++) // O(n)
    {
        travelPoint = travelPoint->next;
    }
    Node *newNode = new Node(element);
    newNode->next = travelPoint->next;
    newNode->prev = travelPoint;
    travelPoint->next = newNode;
    if(newNode->next != nullptr)
        travelPoint->next->prev = newNode;
    else
        tail = newNode;
    size++;    
} 

// 按位置删
void DoubleLinkList::RemoveByIndex(int index)
{
    if(index < 0 || index >= size)
        return;
    Node *travelPoint = head;
    for(int i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }
    Node *freeNode = travelPoint->next;
    travelPoint->next = freeNode->next;
    if(freeNode == tail)
        tail = tail->prev;
    else
        freeNode->next->prev = travelPoint;
    delete freeNode;
    size--;
}

// 按值删
void DoubleLinkList::RemoveByElement(const ElementType &element)
{
    Node *travelPoint = head;
    while(travelPoint->next != nullptr)
    {
        if(travelPoint->next->value == element)
        {
            Node *freeNode = travelPoint->next;
            travelPoint->next = freeNode->next;
            if(freeNode == tail)
                tail = tail->prev;
            else
                freeNode->next->prev = travelPoint;
            delete freeNode;
            size--;
        }
        else
            travelPoint = travelPoint->next;
    }
}

// 按值修改
void DoubleLinkList::UpDateByElement(const ElementType &oldValue, const ElementType &newValue)
{
    Node *travelPoint = head->next;
    while(travelPoint != nullptr)
    {
        if(travelPoint->value == oldValue)
            travelPoint->value = newValue;
        travelPoint = travelPoint->next;
    }
}

// 重载 []
ElementType &DoubleLinkList::operator[](int index)
{
    Node *travelPoint = head; // 从第一个有效数据节点开始
    for(int i = 0; i <= index; i++)
    {
        travelPoint = travelPoint->next;
    }
    return travelPoint->value;
}

// 按值查找
size_t DoubleLinkList::FindByElement(const ElementType &element)
{
    size_t result = 0;
    Node *travelPoint = head->next;
    while(travelPoint != nullptr)
    {
        if(travelPoint->value == element)
        {
            break;
        }
        result++;
        travelPoint = travelPoint->next;
    }
    return result;
}

// 排序
void DoubleLinkList::Sort()
{
    FastSort(head->next, nullptr);
}

// 归并
DoubleLinkList DoubleLinkList::Merge(const DoubleLinkList &list)
{
    DoubleLinkList result;
    Node *p1 = head->next;
    Node *p2 = list.head->next;
    while(p1 && p2)
    {
        if(p1->value < p2->value)
        {
            result.InsertTail(p1->value);
            p1 = p1->next;
        }
        else
        {
            result.InsertTail(p2->value);
            p2 = p2->next;
        }
    }
    while(p1)
    {
        result.InsertTail(p1->value);
        p1 = p1->next;
    }
    while(p2)
    {
        result.InsertTail(p2->value);
        p2 = p2->next;
    }
    return result;
}

size_t DoubleLinkList::Size()
{
    return size;
}

// show
void DoubleLinkList::show()
{
    std::cout<<"size : "<<size<<std::endl;
    Node *travelPoint = head->next; // 存有效数据的第一个节点
    while(travelPoint != nullptr) //当前节点存在
    {
        std::cout<<travelPoint->value<<" "; // 打印数据域
        travelPoint = travelPoint->next; // 访问下一个节点
    }
    std::cout<<std::endl;
}

// 逆序
void DoubleLinkList::ReserveShow()
{
    std::cout<<"size : "<<size<<std::endl;
    Node *travelPoint = tail; 
    while(travelPoint != head) // 排除头节点
    {
        std::cout<<travelPoint->value<<" "; 
        travelPoint = travelPoint->prev; 
    }
    std::cout<<std::endl;
}

// 快排
void DoubleLinkList::FastSort(Node *head, Node *tail)
{
    if(head == tail)
        return;
    Node *temp = head; // 基准值指针
    Node *slow = head; // 慢指针
    Node *fast = head->next; // 快指针
    while(fast != tail)
    {
        // 快指针所指的数据比基准值小
        if(fast->value < temp->value)
        {
            slow = slow->next;
            std::swap(fast->value, slow->value);
        }
        fast = fast->next;
    }
    std::swap(temp->value, slow->value);
    FastSort(head, slow);
    FastSort(slow->next, tail);
}
